package cn.jietuo.first.class05;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2020/7/11
 * @description: 计数排序算法
 */
public class Code02_CountSort {

    public static void countSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // step1: 求出数组中的最大值
        int max = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        // step2: 准备一个help数组
        int[] help = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            help[arr[i]]++;
        }
        int index = 0;
        // step3: 将help数组中的数倒出来
        for (int i = 0; i < help.length; i++) {
            while (help[i]-- > 0) {
                arr[index++] = i;
            }
        }
    }
}

